package bfprt

import (
	"math/rand"
	"time"
)

func MergeSortFindMinK(arr []int, K int) int {
	return MergeSortFindMinKProcess(arr, 0, len(arr)-1, K-1)
}


func MergeSortFindMinKProcess(arr []int, L, R, K int) int {
	if L==R {return arr[L]}
	// 默认 k 再arr内
	l, r := partition(arr, 0, len(arr)-1)
	if K >= l && K <= r {
		return arr[l]
	} else if K < l {
		return MergeSortFindMinKProcess(arr, L, l-1, K)
	} else {
		return MergeSortFindMinKProcess(arr, r+1, R, K)
	}
}

func partition(arr []int, L, R int) (int, int) {
	rand.Seed(time.Now().UnixNano())
	ranM := L + rand.Intn(R-L+1)
	swap(arr, ranM, R)
	less := L-1
	bigger := R
	i := L
	for i < bigger {
		if arr[i] < arr[R] {
			swap(arr, less+1, i)
			less++
			i++
		} else if arr[i] > arr[R] {
			swap(arr, i, bigger-1)
			bigger--
		} else {
			i++
		}
	}

	swap(arr, bigger, R)
	return less+1, bigger
}

func swap(arr []int, i, j int) {
	arr[i], arr[j] = arr[j], arr[i]
}
